package org.laizili.solution.leetcode;

/**
 * <a href="https://leetcode.cn/problems/verifying-an-alien-dictionary/">953. 验证外星语词典</a>
 * <p>
 * tags: 字典序; 自定义排序;
 */
public class Problem953 {
    private static class Solution {
        public boolean isAlienSorted(String[] words, String order) {
            int[] hash = new int[26];
            for (int i = 0; i < order.length(); i++) {
                hash[order.charAt(i) - 'a'] = i;
            }
            for (int i = 1; i < words.length; i++) {
                if (compare(words[i - 1], words[i], hash) > 0) {
                    return false;
                }
            }
            return true;
        }

        // natural order
        private static int compare(String s1, String s2, int[] hash) {
            int len = Math.min(s1.length(), s2.length());
            for (int i = 0; i < len; i++) {
                if (s1.charAt(i) != s2.charAt(i)) {
                    return hash[s1.charAt(i) - 'a'] - hash[s2.charAt(i) - 'a'];
                }
            }
            return s1.length() - s2.length();
        }
    }

    public static void main(String[] args) {
        System.out.println(new Solution().isAlienSorted(new String[]{"ubg", "kwh"}, "qcipyamwvdjtesbghlorufnkzx"));
    }
}
